# -*- coding: utf-8 -*-
"""
| @brief 模拟sort函数
| @author Wuming
| @date 2022-04-04 23:02:58
| @version 1.0.0
"""
import collections
from typing import Iterable, List

# 排序元素结构体
SortElem = collections.namedtuple('SortElem', ['value', 'key'])


def sorted_fake_by_insert(data: Iterable, key=lambda x: x):
    """模拟系统sorted()函数工作过程(插入排序)，方便理解key函数
    functools.cmp_to_key():将cmp_to_key(one,other)转换成key(one)

    :param data:Iterable,可迭代对象
    :param key: function,比较函数，用于确定一个元素的顺序
    :return: list
    """
    result = list(data)
    for i in range(len(result)):
        for j in range(i + 1, len(result)):
            if key(result[i]) <= key(result[j]):
                # result[i] 顺序在 result[j] 之前，不需要交换
                continue
            else:
                # 交换 result[i]、result[j]的内容
                result[i], result[j] = result[j], result[i]
    return result


def sorted_fake_by_quick(data: Iterable, key=lambda x: x):
    """模拟系统sorted()函数工作过程（快速排序），方便理解key函数

    :param data:Iterable,可迭代对象
    :param key: function,比较函数，用于确定一个元素的顺序
    :return: list
    """

    result = [SortElem(i, key(i)) for i in data]
    quick_sort(result, 0, len(result) - 1)
    return [i.value for i in result]


def quick_sort(data: List[SortElem], left: int, right: int):
    """快速排序

    :param data: List[SortElem],要进行排序的序列
    :param left: int,排序区间起始位置
    :param right: int,排序区间结束位置
    :return: void
    """
    if left < right:
        # 划分数组
        pivot = _quick_sort_partition(data, left, right)
        # 对pivot的左边未排序数组进行排序
        quick_sort(data, left, pivot - 1)
        # 对pivot的右边未排序数组进行排序
        quick_sort(data, pivot + 1, right)


def _quick_sort_partition(data: List[SortElem], left: int, right: int) -> int:
    """划分序列,根据data[right]将元素分成2部分，左边部分元素都小于data[right]，右边部分元素都大于data[right]

    :param data: List[SortElem],要进行排序的序列
    :param left: int,排序区间起始位置
    :param right: int,排序区间结束位置
    :return: int，data[right]元素最终所在位置索引
    """
    pivot = data[right]
    i = left - 1
    for j in range(left, right):
        if data[j].key <= pivot.key:
            i += 1
            data[j], data[i] = data[i], data[j]
    data[i + 1], data[right] = data[right], data[i + 1]
    return i + 1
